//1.从尾部到头打印链表
//思路1:从尾部到头修改链表指针指向；(跟面试官沟通)
//思路2:借助辅助函数，栈实现（需要借助额外的空间复杂度）
//思路3:递归实现（需要借助额外的空间复杂度），问题在于链表非常长的时候，导致函数的调用层级很深；
#include <iostream>
#include <vector>
#include <stack>

using namespace std;

struct ListNode {
      int val;
      struct ListNode *next;
      ListNode(int x) :
            val(x), next(NULL) {
      }
};

class Solution1 {
public:
    ListNode* reverselist(ListNode* head){
        ListNode* res;
        ListNode* pre = nullptr;
        ListNode* cur = head;
        ListNode* next = cur->next;
        while(cur != nullptr) {
            next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        return res = pre;
    }
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> res_vec;
        if (nullptr == head) {
            return res_vec;
        }

        ListNode* tail_start_node = reverselist(head);
        while(tail_start_node != nullptr){
            res_vec.emplace_back(tail_start_node->val);
            tail_start_node = tail_start_node->next;
        }
        head = reverselist(tail_start_node);
        return res_vec;
        
    }
};

class Solution2 {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> res;
        stack<int> s;
        //正序输出链表到栈中
        while(head != NULL){
            s.push(head->val);
            head = head->next;
        }
        //输出栈中元素到数组中
        while(!s.empty()){
            res.push_back(s.top());
            s.pop();
        }
        return res;
    }
};

class Solution3 {
public:
    //递归函数
    void recursion(ListNode* head, vector<int>& res){
        if(head != NULL){
            //先往链表深处遍历
            recursion(head->next, res);
            //再填充到数组就是逆序
            res.push_back(head->val);
        }
    }
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> res;
        //递归函数打印
        recursion(head, res);
        return res;
    }
};